package algorithm.templates;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class ArraySortTemplate {

    public static void main(String[] args) {
        int[] testData = {9, 11, 13, 4, 6, 5, 7, 12, 1, 10, 2, 8, 3, 16, 14};
        int[] testDataCopy = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//        new SelectionSort().doSort(testData);
//        new BubbleSort().doSort(testData);
//        new InsertionSort().doSort(testData);
//        new MergeSort().doSort(testData);
//        new BucketSort().doSort(testData);
//        new CountingSort().doSort(testData);
//        new RadixSort().doSort(testData);
//        new RandomQuickSort().doSort(testData);
//        new ShellSort().doSort(testData);

        System.out.println(Arrays.toString(testData));
    }

    /**
     * 希尔排序，gap代表组间数据的间隙
     * 缩小增量排序
     */
    static class ShellSort implements Sort {

        @Override
        public void doSort(int[] array) {
            // 最后一次的gap会缩减为1, 进行最后一次插入排序
            for (int gap = array.length / 2; gap > 0; gap /= 2) {
                for (int i = gap; i < array.length; i++) {
                    int temp = array[i];
                    // jump itself
                    int j = i - gap;

                    while (j >= gap && temp < array[j]) {
                        array[j] = array[j - gap];
                        j -= gap;
                    }
                    array[j] = temp;
                }
            }
        }
    }

    /**
     * 快速排序,和归并排序差不多，本质都是分治的思想
     */
    static class RandomQuickSort implements Sort {

        @Override
        public void doSort(int[] array) {
            quickSort(array, 0, array.length - 1);
        }

        private int quickSortPivot(int[] array, int start, int end) {
            // 使用随机值来尽量避免O(n²)的极端情况
            int randomIndex = new Random().nextInt(start, end);
            swap(array, start, randomIndex);

            int pivot = start;
            int j = start + 1;

            // 保证j标记的左边界最大，小于pivot的都在左侧，大的都在右侧
            for (int i = start + 1; i < end + 1; i++)
                if (array[i] < array[pivot])
                    swap(array, i, j++);

            // 交换大数最左边界的和pivot的数
            swap(array, pivot, j - 1);
            pivot = j - 1;
            return pivot;
        }

        private void quickSort(int[] array, int start, int end) {
            if (start >= end) return;
            int pivot = quickSortPivot(array, start, end);
            quickSort(array, start, pivot - 1);
            quickSort(array, pivot + 1, end);
        }

        private void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    /**
     * 基数排序
     */
    static class RadixSort implements Sort {

        @Override
        public void doSort(int[] array) {
            // base为1，从个位数开始
            int base = 1;
            int max = Arrays.stream(array).max().orElseThrow();

            while (base < max) {
                List<List<Integer>> buckets = new ArrayList<>();
                for (int i = 0; i < 10; i++) {
                    buckets.add(new ArrayList<>());
                }

                // 对数字进行处理，准备放入桶内
                for (int data : array) {
                    // 取出数字最后一位
                    int num = data / base % 10;
                    buckets.get(num).add(data);
                }

                // 将处理后的数字重新取出，变为新的数据
                int idx = 0;
                for (int i = 0; i < 10; i++) {
                    List<Integer> bucket = buckets.get(i);
                    for (Integer value : bucket) {
                        array[idx++] = value;
                    }
                }

                base *= 10;
            }
        }
    }

    /**
     * 计数排序，O(n+k)
     */
    static class CountingSort implements Sort {

        @Override
        public void doSort(int[] array) {
            boolean allPositive = Arrays.stream(array).allMatch(i -> i > 0);
            if (!allPositive)
                throw new RuntimeException("Only all positive numbers are supported");
            int max = Arrays.stream(array).max().orElseThrow();
            int[] countBitmap = new int[max + 1];

            for (int i : array) {
                countBitmap[i]++;
            }

            int idx = 0;
            for (int i = 0; i < countBitmap.length; i++) {
                for (int j = 0; j < countBitmap[i]; j++) {
                    array[idx++] = i;
                }
            }
        }
    }

    /**
     * 桶排序,最理想的情况下为O(n)
     */
    static class BucketSort implements Sort {

        private static final Integer BUCKET_SIZE = 3;

        @Override
        public void doSort(int[] array) {
            int min = Arrays.stream(array).min().orElseThrow();
            int max = Arrays.stream(array).max().orElseThrow();

            int[][] buckets = new int[BUCKET_SIZE][array.length];
            int[] bucketSizes = new int[BUCKET_SIZE];

            double range = (double) (max - min + 1) / BUCKET_SIZE;
            for (int num : array) {
                int index = (int) ((num - min) / range);
                if (index >= BUCKET_SIZE) index = BUCKET_SIZE - 1;
                buckets[index][bucketSizes[index]++] = num;
            }

            int idx = 0;
            for (int i = 0; i < BUCKET_SIZE; i++) {
                selectionSort(buckets[i], bucketSizes[i]);
                for (int j = 0; j < bucketSizes[i]; j++) {
                    array[idx++] = buckets[i][j];
                }
            }
        }

        private void selectionSort(int[] array, int size) {
            for (int i = 0; i < size - 1; i++) {
                int minIdx = i;
                for (int j = i + 1; j < size; j++) {
                    if (array[j] < array[minIdx]) {
                        minIdx = j;
                    }
                }
                int temp = array[i];
                array[i] = array[minIdx];
                array[minIdx] = temp;
            }
        }
    }

    /**
     * 归并排序，O(nlogn)
     */
    static class MergeSort implements Sort {

        @Override
        public void doSort(int[] array) {
            mergeSort(array, 0, array.length - 1);
        }

        /**
         * 递归
         */
        private void mergeSort(int[] array, int start, int end) {
            if (start >= end) return;
            int mid = (start + end) / 2;
            mergeSort(array, start, mid);
            mergeSort(array, mid + 1, end);
            // WTF???头皮发麻，我悟了!
            merge(array, start, mid, end);
        }

        /**
         * 合并
         */
        private void merge(int[] array, int start, int mid, int end) {
            int[] temp = new int[end - start + 1];
            int left = start, right = mid + 1;
            int index = 0;
            while (left <= mid && right <= end) {
                if (array[left] <= array[right]) {
                    temp[index++] = array[left++];
                } else {
                    temp[index++] = array[right++];
                }
            }
            while (left <= mid) {
                temp[index++] = array[left++];
            }
            while (right <= end) {
                temp[index++] = array[right++];
            }
            System.arraycopy(temp, 0, array, start, temp.length);
        }
    }

    /**
     * 插入排序，O(n²)
     */
    static class InsertionSort implements Sort {

        @Override
        public void doSort(int[] array) {
            for (int i = 0; i < array.length; i++) {
                int x = array[i];
                int j = i - 1;
                while (j >= 0 && x < array[j]) {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = x;
            }
        }
    }

    /**
     * 冒泡排序，O(n²)
     */
    static class BubbleSort implements Sort {

        @Override
        public void doSort(int[] array) {
            for (int i = array.length - 1; i >= 0; i--) {
                boolean flag = false;
                for (int j = 0; j < i; j++) {
                    if (array[j] > array[j + 1]) {
                        flag = true;
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
                if (!flag) break;
            }
        }
    }

    /**
     * 选择排序，O(n²)
     */
    static class SelectionSort implements Sort {

        @Override
        public void doSort(int[] array) {
            for (int i = 0; i < array.length - 1; i++) {
                int minIndex = i;
                for (int j = i + 1; j < array.length; j++)
                    if (array[j] < array[minIndex])
                        minIndex = j;
                int temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
        }

    }

    interface Sort {
        void doSort(int[] array);
    }
}